1. Field of the Invention
The present invention relates to techniques for routing an integrated circuit. More specifically, the present invention relates to a physical partition-aware routing technique for routing signal lines through an integrated circuit.
2. Related Art
Advances in semiconductor technology presently make it possible to integrate large-scale systems, including tens of millions of transistors, onto a single semiconductor chip. Integrating such large-scale systems onto a single semiconductor chip increases the speed at which such systems can operate, because signals between system components do not have to cross chip boundaries, and are not subject to lengthy chip-to-chip propagation delays. Moreover, integrating large-scale systems onto a single semiconductor chip significantly reduces production costs, because fewer semiconductor chips are required to perform a given computational task.
As integrated circuit (IC) designers incorporate more system components onto a single IC chip, the complexity of the corresponding IC designs increases. In order to deal with this increased complexity, IC designers typically use “hierarchical” design techniques. During the hierarchical design process, the IC designer initially determines soft physical boundaries, called “physical partitions,” between circuit elements in the design based on hierarchical design placement. Unfortunately, traditional global routing techniques do not report congestion in top-level channels or within physical partitions accurately because they do not understand physical partition boundaries during the initial hierarchical design stage. Furthermore, since pin locations are typically not finalized until later in the design cycle, a poor choice of pin location later in the design cycle can result in long inter-block wires that can cause timing violations which may not be detected until these blocks are finalized.
FIG. 1A illustrates an exemplary partitioning of a layout. It contains chip 100, physical partitions 102, 104, 106, 108, 110, 112, and 114. Note that top-level channels exist between the physical partitions. FIG. 1B illustrates an exemplary partitioning of a layout showing top-level channel congestion. It contains the same elements as FIG. 1A as well as top-level channel congestion 116, 118, 120, 122, and 124. Note that the IC designer receives accurate congestion analysis in the top-level channels and within physical partitions only after finalizing the hierarchical design placement and performing pin assignment on these partitions.
FIG. 2A illustrates a route for a net generated by a traditional global router prior to finalizing hierarchical design. It contains chip 200, partitions 202, 204, and 206, net 208, leaf-level pins 212 and 222, and partition boundary crossings 214, 216, 218, and 220. In one embodiment of the present invention, the system restricts nets from feeding through partition 206. A traditional global router, which does not account for physical partition boundaries and feedthrough constraints during the initial hierarchical design stage, can route net 208 from leaf-level pin 212 to leaf-level pin 222 through partition 206 crossing partition 206 at partition boundary crossings 216 and 218.
FIG. 2B illustrates a route for a net using a traditional global router after finalizing hierarchical design. It contains the same chip 200, partitions 202, 204, and 206, leaf-level pins 212 and 222, and partition boundary crossings 214 and 220 as FIG. 2A, as well as net 210. After the IC designer finalizes the hierarchical design placement, the traditional global router applies the feedthrough constraint of partition 206 and restricts the router from routing net 208 through partition 206, and generates net 210 to connect leaf-level pins 212 and 222. Note that, net 210 only crosses two partitions at partition boundary crossings 214 and 220.
If the IC designer performs congestion analysis on chip 200 during the initial hierarchical design stage after using a traditional global router, the analysis may not report congestion in the top-level channel because the router connects leaf-level pins 212 and 222 through partition 206. After finalizing hierarchical design placement and using the feedthrough constraint over partition 206, the router connects leaf-level pins 212 and 222 using the top-level channel instead of routing over partition 206. Since this new net uses the top-level channel, it may occupy a routing channel already used by another net, thereby causing previously undetected congestion. This congestion can require the IC designer to restart the design process and redo the hierarchical design placement. Therefore, it is desirable for the router to respect any constraints on the routing of nets early in the design process.
FIG. 4 presents a flow chart illustrating a traditional hierarchical design flow. The process begins when the system reads a netlist (step 402). Next, the system generates a hierarchical design placement, which involves placing cells and generating partitions. At this step, the design placement is not a final design placement. Next the design placement is used to check for congestion and timing violations. The system then performs global routing (step 406). Next, the system checks to see if there is congestion (step 408). If there is congestion, the system returns to hierarchical design placement to generate a new placement (step 404). If there are no congestion violations, the system performs in-place optimization (step 410). Next, the system checks for timing violations (step 412). If there is a timing violation, the system returns to hierarchical design placement to generate a new placement (step 404). Otherwise, the system finalizes the hierarchical design placement (step 414).
After finalizing the hierarchical design placement, the system performs block-level and top-level routing (step 416). The system then checks for congestion (step 418). If there is congestion, the system returns to hierarchical design placement (step 404). Otherwise, the system performs in-place optimization (step 420). The system then checks for timing violations (step 422). If there are timing violations, the system returns to hierarchical design placement to generate a new placement (step 404). Otherwise, it performs time budgeting, clock-tree-synthesis (CTS), and detailed block and top-level routing (step 424).
Note that since a traditional global router does not account for the physical partition boundaries while operating during the initial hierarchical design stage, the congestion and timing analysis modules do not report accurate information about these violations during the initial hierarchical design stage. Consequently, the system typically proceeds to the next design flow step even if potential congestion or timing violations exist; these violations will be found in a later design stage. The IC designer obtains accurate congestion and timing analyses only after finalizing the hierarchical design placement (step 414).
Therefore, in order to fix the congestion and timing violations, the IC designer may need to iterate between the initial hierarchical design placement stage, which involves floorplanning and partitioning, and the final hierarchical design placement stage, which involves pin assignment and placement of cells within the partition. Unfortunately, this process is costly and may take a long time to converge.
Hence, what is needed is a method and an apparatus to route nets for an integrated circuit design without the problems described above.